package com.lw.leetcode.stack.c;

import java.util.PriorityQueue;

/**
 * Created with IntelliJ IDEA.
 * stack
 * 295. 数据流的中位数
 * 剑指 Offer 41. 数据流中的中位数
 * 面试题 17.20. 连续中值
 *
 * @author liw
 * @version 1.0
 * @date 2021/11/30 17:58
 */
public class MedianFinder {

    public static void main(String[] args) {
        MedianFinder test = new MedianFinder();
        // ["MedianFinder","addNum","addNum","findMedian","addNum","findMedian"]
        //[[],[1],[2],[],[3],[]]
        test.addNum(1);
        test.addNum(2);
        System.out.println(test.findMedian());
        test.addNum(3);
        System.out.println(test.findMedian());


        // ["MedianFinder","addNum","addNum","findMedian","addNum","findMedian"]
        //[[],[1],[2],[],[3],[]]

    }

    private PriorityQueue<Integer> max;
    private PriorityQueue<Integer> min;
    private int l1 = 0;
    private int l2 = 0;

    public MedianFinder() {
        max = new PriorityQueue<>((a, b) -> Integer.compare(b, a));
        min = new PriorityQueue<>();
    }

    public void addNum(int num) {
        if (l1 == l2) {
            if (l1 == 0 || num <= min.peek()) {
                max.add(num);
            } else {
                max.add(min.poll());
                min.add(num);
            }
            l1++;
        } else {
            if (num < max.peek()) {
                min.add(max.poll());
                max.add(num);
            } else {
                min.add(num);
            }
            l2++;
        }
    }

    public double findMedian() {
        if (l1 == l2) {
            return (double) (min.peek() + max.peek()) / 2;
        }
        return max.peek();
    }

}
